Przejdź do zawartości

Lemat Szanina

Z Wikipedii, wolnej encyklopedii

Lemat Szanina (Δ-lemat, lemat o Δ-systemie) – twierdzenie kombinatoryki nieskończonej udowodnione przez Nikołaja Szanina w 1946 roku[1]. Lemat Szanina nie jest dowodliwy wyłącznie na gruncie aksjomatyki ZF (to znaczy wymaga pewnej formy aksjomatu wyboru)[2].

Twierdzenie

[edytuj | edytuj kod]

Niech κ będzie nieprzeliczalną regularną liczbą kardynalną, X będzie zbiorem mocy κ oraz niech ℬ będzie rodziną skończonych podzbiorów X, która sama ma moc κ. Istnieje wówczas taka podrodzina ℬ0 ⊆ ℬ – również mocy κ – oraz taki zbiór skończony ΔX, że

AB = Δ

dla wszelkich A, B ∈ ℬ0, AB.

Zbiór Δ nazywany bywa czasami korzeniem rodziny ℬ0.

Dowód

[edytuj | edytuj kod]

Bez straty ogólności można przyjąć, że A = κ, tj. w szczególności, rodzina ℬ składa się ze skończonych podzbiorów liczby kardynalnej κ (rozpatrywanej jako początkowa liczba porządkowa). Ponieważ κ ma nieprzeliczalną kofinalność, istnieje taka liczba naturalna n, że rodzina ℬ1 := ℬ ∩ [κ]n jest mocy κ, przy czym symbol [κ]n oznacza rodzinę wszystkich n-elementowych podzbiorów κ. Wystarczy więc udowodnić następujące stwierdzenie:

Niech κ będzie nieskończoną regularną liczbą kardynalną. Wówczas dla każdej liczby naturalnej n oraz każdej rodziny ℬ ⊆ [κ]n mocy κ istnieje taka podrodzina 0 ⊆ ℬ również mocy κ oraz taka liczba porządkowa δ < κ, że dla dowolnych zbiorów A, B ∈ ℬ0, A ≠ B spełniony jest warunek
Aδ = AB = Bδ.

Istotnie, w takim przypadku wystarczy przyjąć Δ = Aδ, gdzie A jest dowolnym elementem rodziny ℬ. Dowód można przeprowadzić indukcyjnie ze względu na n.

  • Gdy n = 1, wystarczy wziąć ℬ0 = ℬ oraz δ = 0 (korzeń rodziny ℬ0 jest pusty).
  • Załóżmy, że stwierdzenie to jest prawdziwe dla pewnego n ≥ 1 i ustalmy ℬ ⊆ [κ]n + 1.
    • Jeżeli istnieje takie τ < κ, że rodzina ℬκ = { A ∈ ℬ: min A = τ } jest mocy κ, to z założenia indukcyjnego istnieje taka rodzina ℬ'0 ⊆ { A \ {τ}: A ∈ ℬ'κ } oraz liczba porządkowa δτ < κ, że Aδτ = AB = Bδτ dla wszelkich A, B ∈ ℬ0, AB. Wystarczy więc przyjąć ℬ0 = {A ∪ {τ}: A ∈ ℬκ} oraz δ = max{δτ, τ}.
    • Gdyby taka rodzina nie istniała, tj. |{ A ∈ ℬ: min A = τ }| < κ dla każdej liczby τ < κ, to można wówczas zbudować rekursywnie funkcję f: κ → ℬ o tej własności, że ∪ f[α] ⊆ min f(α) dla każdego α < κ. Wystarczy wówczas rozważyć ℬ0 := f[κ] oraz δ = 0.
      • Konstrukcja przykładowej funkcji f o powyższych własnościach. Z założenia, dla każdego τ < κ rodzina ℛτ := { A ∈ ℬ: min A = τ } jest mocy (ściśle) mniejszej od κ. Pozwala to zdefiniować rekurencyjnie funkcję g: κκ warunkiem:
g(α) = min [{ τ < κ: ℛτ ≠ ∅ } \ sup ∪ ∪ { ℛσ: σ < sup g[α] }].
dla α < κ. Funkcję f można zdefiniować wybierając za f(α) dowolny element rodziny ℛg(α).

Dowód w oparciu o lemat Fodora

[edytuj | edytuj kod]

Niech ℬ = {Fα: α < κ} będzie rodziną skończonych podzbiorów κ. Podobnie jak powyższym dowodzie, bez straty ogólności można założyć, że każdy zbiór Fα ma dokładnie n elementów dla pewnego n ≥ 1. Gdy n = 1, twierdzenie zachodzi (korzeń Δ jest pusty). Ustalmy ℬ ⊆ [κ]n + 1 mocy κ i załóżmy indukcyjnie, że twierdzenie to zachodzi dla n ≥ 1. Niech f: κκ ∪ {∞} będzie funkcją określoną w następujący sposób: f(α) = min Fα ∩ [0, α), gdy zbiór Fα ∩ [0, α) jest niepusty oraz f(α) = ∞ w przeciwnym przypadku. Gdy f przyjmuje wartość ∞ dla α z pewnego podzbioru κ mocy κ, to możemy wybrać spośród zbiorów {Fα: α < κ} κ zbiorów parami rozłącznych, co dowodzi twierdzenia w tym przypadku. Gdy nie jest to możliwe, bez straty ogólności możemy przyjąć, że funkcja f przyjmuje wartości wyłącznie w κ. Oznacza to, że f spełnia założenia lematu Fodora, ponieważ f(α) < α dla każdego α < κ. Istnieje zatem zbiór stacjonarny Sκ (a więc |S| = κ), na którym funkcja f jest stała, tj. dla pewnego β < κ mamy f(α) = β (αS). W szczególności, βFα dla κ wielu α. Można więc zastosować założenie indukcyjne do rodziny {Fα \ {β}: αS} by otrzymać korzeń Δ' dla pewnej podrodziny ℬ' mocy κ rodziny {Fα \ {β}: αS}. Ostatecznie, wystarczy przyjąć Δ = Δ' ∪ {β} oraz ℬ0 = {A ∪ {β}: A ∈ ℬ'}.

Przypisy

[edytuj | edytuj kod]
  1. N. A. Shanin: A theorem from the general theory of sets. „Доклады Академии Наук СССР” (новая серия), 53 (1946), 399–400.
  2. P. Howard, J. Solski: The strength of the Δ-system lemma. „Notre Dame Journal of Formal Logic”, 34 (1, 1992), 100–106.

Bibliografia

[edytuj | edytuj kod]